The present invention is generally directed to error correction coding and decoding systems. More particularly, the present invention is directed to the incorporation of error correction coding in systems which include parity bits associated with blocks of binary data. Even more particularly, the present invention is directed to a generalized method for constructing error correction codes, encoders, and decoders in a fashion which adds a minimum number of error checking bits while still preserving the code property of correcting single errors and detecting double errors.
Parity bits are commonly used for checking data transfers in computer systems. This parity may be either odd parity or even parity. For purposes of the present invention, there are no restrictions on the form of parity employed. When used in conjunction with memory systems in computers, parity bits employed in the rest of the computer system are often stripped off and entirely replaced by error-checking bits. For purposes of understanding the present invention, it should be appreciated that, while parity bits do provide a form of error correction capability, the term xe2x80x9ccheck bitsxe2x80x9d (or ECC bits herein) is not meant to include parity bits per se in the present discussion. In particular, it is noted that the present invention seeks to encode a number of check bits in addition to the usual parity bits associated with data transfers within a computer system.
However, to provide error correction for data which is stored in a random access memory, the parity bits are usually stripped off and replaced by check bits in a store operation. The check bits that are added are based only upon the data present and the encoding operation of adding redundant bits does not take any advantage of the parity bits which might already be present. In a sense then, the present invention seeks to combine the best features associated with a specific form of error checking, namely, the use of parity bits, in conjunction with more generic forms of redundant bit addition, namely, generic error correction capabilities. The present invention seeks to do this while still maintaining the single error correction and double error detection (SEC-DED) capabilities for the encoding while at the same time using the minimal number of added check bits.
When the parity bits are stripped off during a store operation, the parity to ECC (error correction code) and the ECC-to-parity conversion are often not done, primarily for speed consideration. In these cases, the ECC bits are generated on top of the parity bits. However, since parity bits can be used as part of an overall ECC checking system, the additional redundant bits required for ECC can be reduced from the number required when no parity bits are available.
In particular, one of the purposes of the present invention is to provide a generic method for constructing encoding systems, decoding systems, and memory systems for various sizes of data path widths and memory organizations. Even more particularly, the present invention provides a mechanism in which parity bits and check bits resulting from a read operation may be corrected independently from one another. Furthermore, in doing so, it is applicant""s intention to provide simpler and faster circuits for performing these operations.
Of particular relevance in this area, U.S. Pat. No. 4,345,328 issued to Gary White on Aug. 17, 1982, describes an encoding scheme which uses five ECC check bits to correct single errors and to detect double errors for a group of 36 data bits with four parity bits in each subgroup of nine data bits. However, the teachings of White are lacking in a description of any kind of general method for generating ECC check bits when pre-existing parity bits exist. Furthermore, the coding method described in the patent to White does not detect multiple odd numbers of errors. Lastly, but most importantly, the decoding of bit error positions in the patent to White is based upon the entire data group and correspondingly is much more complex in its implementation. In contrast, the encoding and decoding methods of the present invention provide a mechanism in which errors can be indicated as occurring in a specific one of the parity bits or in a specific non-parity bit (that is, in a data bit) or even, if desired, in one of the ECC bits.
In accordance with a preferred embodiment of the present invention, a method for encoding binary data arranged in t blocks of m+1 bits each, with each block including a parity check bit, mt bits are encoded using a binary parity check matrix H which adds r check bits in addition to the t parity bits already present so as to permit decoding of the resultant mt+t+r bits so that determination of bit error positions is performable on individual blocks of m+1 bits as a result of the structure of the parity check matrix which maintains a separation of check bits and already existing parity bits.
The present invention also includes an electrical circuit for encoding input from electrical signals representing binary data arranged in t blocks m+1 bits each with each block also including at least one parity bit, through the utilization of a parity check matrix H of the form (M M . . . M I) where M is an r by m matrix and I is an r by r identity matrix. In such a system, the circuit adds a total of r check bits which is in addition to the already existing t parity bits in each block.
In yet another embodiment of the present invention, an apparatus for error correction for binary data arranged in t blocks of m+1 bits with an additional r check bits comprises a parity check for each of the t blocks and a syndrome generator which is constructed in accordance with the parity check matrix used to encode the binary data. Furthermore, the decoding apparatus of the present invention includes a first circuit means for determining that a single error has occurred in the parity bits based upon an xe2x80x9call-zeroxe2x80x9d output from the syndrome generator and an indication from the parity checkers for the presence of one and only one parity error in the t blocks of data. The apparatus for error correction also includes a second circuit means for determining that a single non-parity error has occurred in one of the t blocks based upon a non-zero output from the syndrome generator and an indication from the parity checker for the presence of one and only one parity error in the t blocks of data.
In yet another embodiment of the present invention, a memory system comprises an array of addressable storage locations for binary data wherein the locations are capable of storing t blocks of data with m+1 bits in each block plus an additional r check bits. A digital encoding circuit appends r check bits to the (m+1)t bits of data prior to storage in one of these storage locations. Each block includes at least one parity bit. Additionally, a digital decoding circuit receives mt+t+r bits of data from storage locations and the decoding circuit is configured so as to be capable of independently indicating whether a single error has occurred in a specific one of the parity bits or in a specific non-parity bit. Furthermore, these error indications do not rely on an analysis of the entire data group. This indication is made possible as a result of the specific digital encoding for the r check bits which is implemented by the encoding circuit which is based on the parity check matrix described herein.
Accordingly, it is an object of the present invention to add ECC check bits to a block of data which already includes parity check bits associated with individual subgroups of the block of data.
It is also an object of the present invention to add ECC check bits to data which already includes parity bits in a cooperative and consistent manner.
It is a still further object of the present invention to generalize the construction of encoding and decoding circuits for check bit encoding and error detection and correction, particularly in computer memory systems.
It is a still further object of the present invention to add the minimum number of check bits needed to preserve SEC-DED code capabilities.
It is yet another object of the present invention to simplify the construction of ECC decoder circuitry.
It is also an object of the present invention to establish a cooperative relationship between parity check bits and more generically applicable ECC check bits.
It is a still further object of the present invention to provide a decoding system and method in which the decoding of bit error positions is not based upon the entire data group.
It is also an object of the present invention to provide a decoding system, method, and algorithm which is modular in structure and which provides substantially the same logic circuit construction for each subgroup.
It is a still further object of the present invention to provide an error encoding and decoding system and method in which multiple odd errors are detected.
It is yet another object of the present invention to provide a memory system in which there is a cooperative relationship between parity bits present in incoming data and ECC check bits present in the structure of the memory system.
Lastly, but not limited hereto, it is an object of the present invention to extend the error correction capabilities associated with memory systems and, in particular, those memory systems which preserve SEC-DED error correction capabilities.